package day04;

import java.util.Comparator;
import java.util.Objects;

public class MyPriorityList<T extends Comparable<T>> {

    private static class Node<T extends Comparable<T>> {
        private T value;
        private Node<T> next;

        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }

        public Node(T value) {
            this(value, null);
        }

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

        public Node<T> getNext() {
            return next;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }
    }

    private Node<T> head;
    private int size;
    private final Comparator<T> comparator;

    public MyPriorityList(Comparator<T> comparator) {
        this.comparator = Objects.requireNonNull(comparator);
        this.head = null;
    }

    public Node<T> getHead() {
        return head;
    }

    public void setHead(Node<T> head) {
        this.head = head;
    }

    // 链表新增节点
    public void add(T t) {
        final Node<T> node = new Node<>(t);
        Node<T> current = this.head;
        Node<T> prefix = null;
        // 循环判断新增节点的大小，如果大于当前节点，就继续循环，直到找到比新增节点大的。这就能确定它可以放在哪个位置
        while (current != null && t.compareTo(current.getValue()) > 0) {
            prefix = current;
            current = current.getNext();
        }
        // 上个节点为空，则为初始节点，新增节点当作头节点
        if (prefix == null) {
            this.head = node;
        } else {
            // 上一个节点的next节点赋值为新增节点
            prefix.setNext(node);
        }
        // 新增节点的next节点赋值为比它大的current
        node.setNext(current);
        // 自增长度
        this.size++;
    }

    @Override
    public String toString() {
        Node<T> node = this.head;
        final StringBuilder stringBuilder = new StringBuilder("[");
        while (node != null) {
            stringBuilder.append(node.getValue()).append(",");
            node = node.getNext();
        }
        if (stringBuilder.length() > 1) {
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    public T popFirst() {

        if (this.head == null) {
            throw new IndexOutOfBoundsException("out");
        }
        Node<T> current = this.head;
        this.head = current.getNext();
        this.size--;
        return current.getValue();
    }
}

class Go {

    public static void main(String[] args) {

        MyPriorityList<Integer> list = new MyPriorityList<Integer>(
                Comparator.comparingInt(o -> o)
        );
        list.add(1);
        list.add(44);
        list.add(33);
        list.add(2);
        list.add(55);

        System.out.println(list);
        System.out.println("---------------");
        System.out.println(list.popFirst());
        System.out.println("---------------");
        System.out.println(list);
    }

}
